The problem of securely delegating computational tasks to untrusted third parties comprises a particularly active research area. Generally speaking, secure delegation involves the design of protocols that allow the controlled authorization for an otherwise untrusted party to compute a given function while achieving some target security property (e.g., the verifiability of results or privacy of inputs/outputs) and also preserving the efficiency of the protocols so that the delegation itself remains meaningful. A number of specific cryptographic primitives have been considered in this context.
U.S. patent application Ser. No. 13/334,709, filed Dec. 23, 2011, entitled “Methods and Apparatus for Generating Forward Secure Pseudorandom Numbers,” (now U.S. Pat. No. 9,008,303), incorporated by reference herein, discloses forward-secure pseudorandom generators (FS-PRNGs) that are forward secure as well as efficient with respect to their key-update processes. Pseudorandom functions (PRFs) are a fundamental primitive for emulating perfect randomness via keyed functions that find numerous applications in information security. Nonetheless, PRFs have not been provided in the context of delegation of computations (of PRF values).
Thus, a need remains for a delegatable pseudorandom function (DPRF) cryptographic primitive that enables the delegation of the evaluation of a pseudorandom function (PRF) to a proxy according to a given predicate that defines the inputs on which the proxy will evaluate the PRF.